Informatik Grundlagen
Informatik Grundlagen Bitte hier Fragen/Antworten/Bilder usw. posten! Hauptüberschriften mit zwei Ist-Gleich-Zeichen Unterüberschriften mit drei Ist-Gleich-Zeichen Informatik Grundlagen (Theorie) ---- binäres Rechnen Addition zwei positive Zahlen: einfach addieren zwei negative Zahlen: binär mit Vorzeichen: einfach addieren (wobei man für binäre Darstellung mit Vorzeichen beachten muß: das Vorzeichen: die erste Ziffer einfach unbeachtet lässen) Exzess: einfach addieren, wenn man dann die tatsächliche dezimale Zahl haben will einfach: Zahl=Zahlenwert-127 Einerkomplement: erste Zahl lassen von zweiter Zahl Einerkomplment bilden addieren Zweierkomplement: erste Zahl lassen von zweiter Zahl Einerkomplement bilden bei zweiter Zahl 1 dazuzählen addieren Zahl=Ergebnis+1 Subtraktion am Besten: positive und negative Zahl: von der jeweiligen negativen Zahl Einerkomplement bilden und addieren Achtung: bei zwei z.B.: 8-Bit-Zahlen darauf achten: wenn man plötzlich statt 8 Ziffern 9 Ziffern hat, muß die Ziffer ganz links gestrichen werden, sonst ist das Ergebnis falsch!!! bei Exzesszahlen: die eine Zahl von der anderen abziehen (Einerkomplement macht hier entweder keinen Sinn oder ist zuviel Aufwand) Multiplikation Multipliokator als Binärziffer anschreiben, dann, wie bei der händischen Dezimalmultiplikation multiplizieren: 64*2=128 01000000*10 ____________ 1000000 00000000 _________ 010000000=128 oder: 67*3=201 01000011*11 ___________ 01000011 01000011 __________ 011001001=1+8+64+128=201 gilt auch bei Exzessdarstellung und Einerkomplement, bei Zweikomplement, sollte man dann ei wenig aufpassen Division Division ist an und für sich eine umgekehrte Multiplikation am leichtesten tut man sich wahrscheinlichj, wenn man den Dividenden als Kehrwert interpretiert und mit diesem dann multipliziert, und dann, die Stellen hinter dem Komma der Zahl, mit der man multipliziert hat, von hinten her durchzahlt, und beim Ergenis das Komma von hinten her gezählt, an dieselbe Stelle setzt: 127:32=3,96875 01111111:00100000 1111111*0,00001 ___________________ 0000000 0000000 0000000 0000000 0000000 1111111 ________________ 0000011,11111 (Kontrolle: 2+1+0,5+0,25+0,125+0,0625+0,03125=3,96875) Man kanns natürlich auch einfach dividieren 1111111:100000=11,11111 (-100000) 01111110 (-100000) 001111100 (-100000) 0001111000 (-100000) 00001110000 (-100000) 000001100000 (-100000) 0000001000000 (-100000) 00000000000000 Michael: Wie verhindere ich denn, daß ich die gestrichelte Umrandung bekomme *treuherzig in die Runde blick* ---- Zahlen umwandeln aus binär in dezimal durch bilden von 2er Potenzen, zb: 10011101=1*2^7+0*2^6+0*2^5+1*2^4+1*2^3^+1*2^2+0*2^1*^*2^0=128+0+0+16+8+4+0+1=157 aus binär in oktal Zusammenfassen von jeweils 3 Binärstellen, dann die Zahl des jeweiligen Teils ausrechnen und als Ziffer anschreiben: 10011101=10 011 101=235 (Kontrolle: 2^7+2^4+2^3+2^2+2^0=128+16+8+4+1=157 und 2*8^2+3*8^1+5*8^0=2*64+3*8+5*1=128+24+5=157) aus binär in Hexadezimal Zusammenfassen von jeweils 4 Binärstellen, dann die Zahl des jeweiligen Teils ausrechnen und als Hexadezimalziffer anschreiben: 10011101=1001 1101=9D (Kontrolle Dezimal 157 und 9*16^1+13*16^0=144+13=157) aus binär in dezimal, Einerkomplement, Zweierkomplement und Betrag Binär zu Dezimal: wurde schon beschrieben. Einerkomplement: ersetzen aller 0 durch 1 und aller 1 durch 0 Zweierkomplement: Einerkomplement + 1 (Michael:'''es gibt noch eine andere Möglichkeit, aber die kann ICH mir nicht merken Betrag: bei positiven Zahlen die Ziffernfolge bei negativen Zahlen kommt es auf die Darstellungsweise an: Exzessdarstellung ist anders zu handhaben, wie Einer- oder Zweierkomplement. Deswegen ist mir diese Frage ohne eine konkrete Zahl schleierhaft ---- Negative Zahlen ganz einfach: 1 000 -7 0 111 7 hier macht das Einerkompliment Sinn man bildet vom Betrag (Binärzahl ohne VZ) das EK und rechnet es aus, schon hat man den gültigen Betrag, setzt ein minus davor weil man ja im Hinterkopf behalten hat dass es eine negative Zahl ist 0 VZ = positiv 1 VZ = negativ '''Michael: stimmt nicht nicht ganz, glaube ich, denn in der Binärdarstellung: +7=00000111 -7=10000111 Exzessdarstellung: -7=127-7=120 -> 64+32+16+8 -> 2^6+2^5+2^4+2^3=0111000 +7=127+7=134 -> 128+4+2 -> 2^7+2^2+2^1=10000110 +7=10000110 -7 0111000 Einerklomplement: +7=00000111 -7=11111000 Zweierkomplement: +7=00000111 -7=11111001 Die gleichen negativen Zahlen sehen also jedesmal anders aus, bei Exzessdarstellung sogar die positive Zahl: aufpassen!!! ---- Rechnung Beispiel * Interpretieren sie folgende Bitkombination 11101011 als Binärzahl. Binärzahl mit Vorzeichenbit. Exzessdarstellung. Einerkomplement und Zweierkomplement und geben sie die jeweiligen Werte als Dezimalzahlen an. Dezimalzahl: 1*128+1*64+1*32+16*0+8*1+4*0+2*1+1*1=235 oder was sich bei der Zahl eher anbietet: 255 - 4*1 - 16*1 = 235 Unter Berücksichtigung des VZbits: 1=negativ 11101011 EK = 00010100 = 4*1 + 16*1 = 20 sprich -20 das gleiche mit Vorzeichenbit = 235 - 128 (erste Stelle wird für das Vorzeichen verwendet) = 107-127 = -20 * Geben sie für die folgende Zahl die normalisierte binäre Gleitkommadarstellung (insgesamt 10 Bit; Exponent: 3 Bit; Exzessdarstellung) an: -2,0625 Wilfried: HIIILFEEEEE!! Kann man das Beispiel hier wirklich lösen? Für mich ergibt sich aus der Zahl -2,0625 die binäre Schreibweise 1101,0001 bzw. normalisiert 0,11010001.2^4 Insgesamt stehen 10 Bit zur Verfügung (abzügl. 1 fürs Vorzeichen und abzügl. 3 für den Exponenten) Die Darstellung der Mantisse geht sich aber mit den verbleibenden 6 Bit nicht aus, oder bin ich da komplett am Holzweg?? Wilfried Ende Michael: Ja kann man -2,0625 = - (2^1+2^-4=1/1) also binär -10,0001 und normalisiert 0,100001 <- da das so definiert ist, daß in normalisierter Darstellung die erste 1 immer hinter dem Komma steht, kann ich das dann auch dann so schreiben: 100001 die Exzessdarstellung wird (so habe ich mich informiert) nur im Exponenten verwendet, also habe ich für den Exponenten die Bereiche (2^x+1) erste Stelle (2^x) zweite Stelle (2^x-1) dritte Stelle zur Verfügung der Exponent sagt mir jetzt binär, welchen Stellenwert die Zahl hat. In der Exzessdarstellung verschiebe ich die 0 so, daß sie eigentlich die kleinste darstellbare negative Zahl ist, bei 3 Bit heißt das, die kleinste Darstellbare Zahl=-2 (000) die größte +3 (110), 2 ist dann (100). In diesem Beispiel wollen wir zeigen, daß die erste Stelle unserer Mantisse (die Zahl 100001), eigentlich eine 2 ist, also 2^1. also ist der Exponent: 100 damit haben wir mit dem Vorzeichen 1 für -, die Zahl: 1 100 100001 (Vorzeichen Exponent Mantisse) Die Zahl in ihrer binären Darstellung hat jetzt genau 10 Stellen und ist genau -2,0625 Ich hoffe, daß ich nicht wieder einmal a) zu kompliziert war, und b) daß, das Ergebnis auch wirklich richtig ist --- Michael: das Folgende gehört nicht mehr zu meinem Geschreibsel, aber ich lasse es drin, denn ich persönlich finde es nicht gut, anderen über den Mund zu fahren, und nichts anderes wäre es, wenn ich das löschen würde ... (auch wenn man mich sonst oft erwischt, daß ich das tue: ist ein Überbleibsel aus Zeiten, als ich mir noch nichts dabei dachte ... und alte Gewohnheiten *seufz*) wie wird das berechnet? nun endlich die Lösung: -128 = 0 -127 = 1 -1 = 2^7-1 0 = 2^7 +1 = 2^7+1 +126 = 2^8-2 +127 = 2^8-1 ich hoffe diese Bsp. auf 8 bit mit VZ-bit helfen weiter. konkretisiert heißt das bei 11101011 also 2^8-1 - 2^4 - 2^2 Quelle: http://www.auto.tuwien.ac.at/~schi/LVAs/GdIue/GdI-UE2-2.pdf ---- Algorithmus - Nennen sie die allgemeinen Kennzeichen eines Algorithmus 1. Aufbau aus einzelnen Schritten * Jeder Schritt bezeichnet eine Tätigkeit (Operation, Befehl). * Einzelne Schritte können zu Teilalgorithmen zusammengefasst werden. ( was nicht bedeutet, dass Teilalgorithmen eigenständig sinnvoll funktionieren müssen, damit sind in der heutigen Zeit vor allem Funktionen und Klassen gemeint) 2. Verständlichkeit * Jeder Schritt muss dem, der ihn ausführen soll, verständlich sein. (Also dem Rechner/Terminal/Server/sonstigem Gerät) 3. Eindeutigkeit * welche Tätigkeit (was soll gemacht werden) * wie soll die Tätigkeit ausgeführt werden * welcher Folgeschritt 4. Ausführbarkeit * Der Ausführende muss den Schritt tatsächlich durchführen können. 5. Endlichkeit * statisch: endlicher Text, endliche Anzahl von Schritten * dynamisch: Ausführung in endlicher Zeit möglich 6. 0 oder mehr Eingangsgrößen, 1 oder mehr Ausgangsgrößen ---- Darstellungs- und Modellierungskonzepte Was versteht man unter den Begriffen „Modellierungskonzept“ und „Darstellungskonzept“? Erklären sie diese Begriffe anhand eines von ihnen wählbaren Paradigmas von Programmiersprachen. ---- Rechnerarchitektur - Nennen sie alle Von-Neumann-Prinzipien der Rechnerorganisation Im Jahre 1946 von John von Neumann vorgeschlagenes Konzept zur Gestaltung eines universellen Rechners, der technischen, wissenschaftlichen und kommerziellen Anforderungen gerecht wird. Von einigen wenigen Ausnahmefällen ... abgesehen, orientieren sich die heutigen Rechenanlagen an der Struktur dieses klassischen Universalrechners. Der Rechner ist nach folgenden Prinzipien ... aufgebaut:” 1. Der Rechner ist logisch und räumlich eingeteilt in: Speicherwerk, Leitwerk, Rechenwerk, Ein- / Ausgabewerk 2. Universalrechner (Programmsteuerung); Rechner ist unabhängig vom Problem) 3. Gleichheit von Daten und Programmen (Programme, Daten, Zwischen- und Endergebnisse werden im selben Speicher abgelegt) 4. Adress-Speicherung (Speicher ist in Zellen unterteilt und numeriert. Über die Nummer (Adresse) kann der Inhalt bearbeitet werden) 5. Sequenzielle Programmspeicherung 6. Verfügbarkeit von Adress-Sprüngen 7. Verfügbarkeit bedingter Sprungbefehle 8. Verwendung des dualen Zahlensystems (binär) John von Neumann: US-amerikanischer Mathematiker österreichisch-ungarischer Herkunft; schuf die wesentlichen theoretischen Grundlagen für programmgesteuerte Automaten, denen heute alle Digitalrechner gehorchen Moores Law: ca. alle 18 Monate verdoppelt sich der RAM (Speicherkapazität) ca. alle 3 Jahre verdreifacht sich die Geschwindigkeit von Prozessoren (CPU) da wir momentan an die physikalischen Grenzen stoßen, flacht diese Funktion zunehmend ab. Unterschied RISC/CISC und wieso beide Systeme verschmelzen. RISC ist einfacher gehalten, setzt also auch einfachere Hardware vorraus. CISC kann schwierigere Prozesse in einem Zyklus erledigen. Für einfache Prozesse ist RISC also klar performanter, für schwere Prozesse CISC. Es ist eine eigene Philosophie und man versucht Schritt für Schritt beide zusammen zu führen. Beide können das gleiche in situationsabhängiger Geschwindikeit, nur der Compiler ist unterschiedlich, ein C++-Programmierer merkt beim programmiern keinen Unterschied. Was ist Caching? Es wird ein 2-3 strufiges Cachesystem eingesetzt: L1 (level 1)direkt am Prozessor/L2 (level 2) nahe am Prozessor. Wieso Caching? Cache ist kleiner als Arbeitsspeicher, dafür weit schneller und teurer(bei Zugriffszeit). Welcher Speicher ist am schnellsten und dafür am teuersten? Register -> Cache -> Arbeitsspeicher -> Plattenspeicher Was gibt es bei einem Bussystem zu beachten? Es gibt immer einen Master der eigenständig am Bus aktiv werden kann und gegebenenfalls einen Slave. Jedes Motherboard hat 2 IDE/E-IDE Controller, sprich 4 Geräte können standardmäßig angeschlossen werden. Bsp. IDE-Bus Platte 1 Master - Platte 2 Slave Platte 1 Master - Cd-rom-Laufwerk Slave zum Vergleich (nur Zusatzinformation): Bsp. SCSI 1 HOST (Controller) und je nach System 7-15 mögliche Targets in Ringnetz ---- Übersetzer * a.) Was versteht man unter einem Compiler, Interpreter, Assembler? Alle drei sind sogen. Sprachprozessoren. Der Assembler ist ein Programm, der ein in einer Assemblersprache geschriebenes Programm in die Maschinensprache übersetzt. Der Compiler ist ein Programm, der ein in einer höheren Programmiersprache geschriebenes Programm in die Maschinensprache übersetzt. Die Module eines Compilers siehe nachfolgend in Punkt b.) Qualitätskriterien sind u.a. die Effizienz der Übersetzung und des erzeugten Maschinenprogramms sowie die Robustheit. Der Interpreter ist ein Übersetzungsprogramm für höhere Programmiersprachen, das keinen Maschinencode erzeugt, es übersetzt Anweisung für Anweisung und führt jede Anweisung sofort aus. * b.) Nennen und erklären sie kurz die Aufgaben der Module eines Übersetzers: 1. Lexikalische Analyse filtert Morpheme und deren Informationen (Code, Wert, Symbolposition) aus dem Quelltext 2. Syntaktische Analyse Prüfung der syntakt. Korrektheit, Gruppierung der Morpheme zu Einheiten, Aufbau des Parse-Baums 3. Semantische Analyse Überprüfung der semant. Regeln (z.B. Typ des Ausdrucks auf rechter Seite entspricht Typ der Variable auf linker Seite), Aufbau von Datenstrukturen, die zur Code-Erzeugung notwendig sind 4. Codegenerierung Eingabe: Parse-Baum, Symboltabelle / Ausgabe: Code in Zielsprache (Maschinen-, Zwischen-, Assemblersprache) 5. Codeoptimierung Einsatz von Regeln, die den Code effizienter machen, z.B. Belassen von Daten in Registern, Umreihen von Operationen, Entfernen unnötiger Operationen (Eliminierung von Wiederholungen, …) ---- Betriebssysteme Was ist ein Deadlock? Nennen und beschreiben sie die für einen Deadlock notwendigen Bedingungen: Eine Menge von Prozessen verursacht einen Deadlock, wenn jeder einzelne von ihnen auf etwas wartet (Betriebsmittel, Ereignis), was nur durch eine Aktivität eines (anderen) Prozesses eintreten kann. Notwendige Bedingungen für Deadlocks: − mutual exclusion ein Betriebsmittel kann zu jedem Zeitpunkt höchstens von einem Prozess belegt sein. − resource waiting wenn ein angefordertes Betriebsmittel besetzt ist, wird der Prozess blockiert. − partial allocation Prozesse, die bereits Betriebsmittel haben, können die Zuteilung weiterer anfordern. − non preemption zugeteilte Betriebsmittel müssen vom Prozess explizit freigegeben werden (können nicht zwangsweise entzogen werden) Das verhindern von Deadlocks ist sicher sehr wichtig, aber ich glaube bei BS ist mehr wichtig :) Ich mach einfach mal additiv, was ich wichtig finde: Das Operating System (BS) ist auf der Programm-Ebene. Abstraktion: Hardware <-> Software Schnittstellen Ressourcemanagement von CPU - Speicher - anderen Einheiten wie zB. Laufwerke mit dem Ziel einer hohen Verfügbarkeit Security: Sicherheit vor Hackern, bestmöglicher Schutz vor Speicherfehlern Bsp. für die wichtigsten Betriebssysteme: UNIX - Windows - Dos Einprogrammbetrieb (veraltet, was zu DOS-zeiten gebräuchlich) Batch: Spool: Time-Sharing: Netzwerkbetriebssysteme: Scheduling/Dispatching: Wichtige Strategiemerkmale: Fairness - Effizienz - Durchsatz - Antwortzeiten - geringer Overhead ---- Turingmaschine Gegeben sei eine deterministische Touringmaschine T mit folgenden Eigenschaften: - Menge der Zustände: {Z0, Z1, Z2, Z3, Z4, Z5, Z6, Z7, Z8, Z9, Z10}, - Startzustand: Z0, - Menge der Endzustände: {Z10}, - Eingabealphabet: {a, b, c, I, B}, - Leersymbol (Blank): B, - Übergangsfunktion: Ausgangszustand Zielzustand Lesesymbol Schreibsymbol Leserichtung Z0 Z1 a B R Z1 Z2 b B R Z2 Z2 a a R Z2 Z2 b b R Z2 Z3 c c R Z3 Z3 I I R Z3 Z4 B B L Z4 Z5 I B L Z5 Z5 I I L Z5 Z6 c c L Z6 Z6 a a L Z6 Z6 b b L Z6 Z7 B B R Z7 Z8 a B R Z7 Z9 c c R Z8 Z2 b B R Z9 Z10 B B L Stellen sie für folgende mit Leersymbolen umgebenen Wörter nachvollziehbar (dokumentiert durch die Folge der Zustände) fest, ob die Turingmaschine (nach Allan Turing) hält, wenn sie im Ausgangszustand am ersten Symbol des Wortes steht: abcI, bababcI, abaaabbcIIII, ababcIII Zur Lösung die eckige Klammer umschließt alle Zeichen, die die Turingmaschine durchläuft, ohne daß eine Änderung des Zustands oder Ersetzung des Zeichens geschieht abcI: Z0:abcIB-> Z1:BbcIB-> Z2:BBcIB-> Z3:BBcIB-> Z4:BBcIB-> Z5:BBcBB-> Z6:BBcBB-> Z7:BBcBB-> Z9:BBcBB-> Z10:BBcBB Turingmaschine erreicht Endzustand und hält bababcI: Z0: bababcI --> aus Turingmaschine erreicht den Endezustand nicht abaaabbcIIII: Z0:abaaabbcIIIIB-> Z1:BbaaabbcIIIIB-> Z2:BBaaabbcIIIIB-> Z3:BBaaabbcIIIIB-> Z4:BBaaabbcIIIIB-> Z5:BBaaabbcIIIBB-> Z5:BBaaabbcIIIBB-> Z6:BBaaabbcIIIBB-> Z7:BBaaabbcIIIBB-> Z8:BBBaabbcIIIBB --> aus Turingmaschine erreicht den Endzustand Z10 nicht ababcIII: Z0:ababcIIIB-> Z1:BbabcIIIB-> Z2:BBabcIIIB-> Z3:BBabcIIIB-> Z4:BBabcIIIB-> Z5:Z4:BBabcIIIB-> Z6:Z4:BBabcIIIB-> Z7:BBabcIIIB-> Z8:BBBbcIIIB-> Z2:[BBBBcIIIB-> Z3:BBBBcIIIB-> Z4:BBBBcIIIB-> Z5:BBBBcIIBB-> Z6:BBBBcIIIB-> Z7:BBBBcIIIB-> Z9:BBBBcIIIB ---> aus Turingmaschine erreicht Endzustand Z10 nicht ---- Anforderung an eine Programmiersprache 1. Klarheit des Sprachkonzeptes (soll einfach zu verwenden sein) 2. Klarheit der Programmstruktur (syntax und Semantik) 3. Unterstützung moderner Software-Techniken 4. Erweiterbarkeit 5. Natürlichkeit für die Anwendung (Datenstrukturen und Programmstrukturen) 6. Portabilität und Kompatibilität (Linux < > Windows) 7. Effizienz 8. Externe Unterstützung z.B: pretty printer ---- Generationen von Programmiersprachen * 1. Generation: Maschinensprachen * 2. Generation: Assemblersprachen(ASM) * 3. Generation: höhere Programmiersprachen (zB. C++, Turbo Pascal) * 4. Generation: noch näher zum Problem hin (z.B. SQL) ---- Schritte zur Lösung von Problemen 1. Erkennen der Problemstellung 2. Abstraktion (Was?) 3. Entwurf eines Lösungsalgorithmus (wie?) 4. Nachweis der Korrektheit des Algorithmus 5. Codierung 6. Test und Fehlerbeseitigung 7. Dokumentation ---- Boolesche Algebra beruht auf logischen Ausdrücken 1. einfachste elementare Aussagen true: wahre Aussage (1) false: falsche Aussage (0) 2. logische Operatoren binär: Konjuktion: und (and) Disjunktion: oder (or) unär: Negation: nicht (not) 3. Wahrheitstafeln 4. Gesetze Involutionsgesetz Verneinung: nicht nicht x = x Kommutativgesetz: x und y = y und x, x oder y= y oder x Assoziativgesetz: (x und y) und z=x und (y und z), (x oder y) oder z=x oder (y oder z) Idempotenzgesetz: x und x=x, x oder x=x Absorbtionsgesetz: x und (x oder y)=x, x oder (x und y)=x Distributivgesetz: x und (y oder z)=(x oder y) und (x oder z), x oder (y und z)=(x oder y) und (x oder z) De Morgan-Gesetz: nicht(x und y)= nicht x oder nicht y, nicht (x oder y)= nicht x und nicht y Neutralitätsgesetz: x oder (y und nicht y)=x, x und (y oder nicht y)=x x oder 0=x (weil y und nicht y immer falsch ist), x und 1=x (weil y oder nicht y immer wahr ist) ---- Kontakte Kontakte ----